"""
Programming Assignment 1
ICE1210, Algorithm Design and Analysis, Fall 2007
Youmin Kim (20041025)

1. Introduction
We implement some sorting algorithms: merge, quick, heap, radix sort in python.

2. Environment
 - download python 2.5 (see www.python.org/)
 - set it up
 - command "$python 20041025sort.py --{merge|quick|heap|radix}sort <name>.dat"

3. Implementation deatail
 - mergesort: sentinel value is supposed to '999999'
 - heapsort: global variable 'heapSizeOfA' is used. It measn heap-size[A]
 - quicksort: none
 - radixsort: we supposed that input data is not over 10000. We implement a formatting to make up digits and insertion sorting algorithm is used as the stable sorting algorithm. 

Note that we neglect index 0 of all lists for transparency between psuedo-code and implementation. 

4. References
 - Guido van Rossum, "Python Tutorial", http://www.python.org/doc/2.4.1/tut/tut.html
"""


import sys

def merge(A, p, q, r):
    n1 = q - p + 1
    n2 = r - q
    L = []
    R = []
    
    # index 0 is neglected 
    # the reason is competability with pseudo-code in reference book
    L.insert(0,'')
    R.insert(0,'')
    for i in range(1, n1+1):
        L.insert(i,A[p+i-1])
    for j in range(1, n2+1):
        R.insert(i,A[q+j])
    
    # sentinel value is supposed to '999999'
    L.insert(n1+1,999999)
    R.insert(n2+1,999999)
    i = 1
    j = 1
    print "\tL=",L
    print "\tR=",R
    for k in range(p, r+1):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
    print "\t=>",A

def mergeSort(A,p,r):
    if p < r:
        q = (p+r)/2
        print
        print "mergeSort(A,",p,",",q,")"
        print "A=",A
        mergeSort(A,p,q)
        print
        print "mergeSort(A,",q+1,",",r,")"
        print "A=",A
        mergeSort(A,q+1,r)
        print
        print "\tmerge(A,",p,",",q,",",r,")"
        print "\tA=",A
        merge(A,p,q,r)


# global variable meaning of heap-size[A]
heapSizeOfA = 0
def maxHeapify(A,i):
    global heapSizeOfA
    l = 2*i
    r = 2*i + 1
    largest = 0
    if l <= heapSizeOfA and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r <= heapSizeOfA and A[r] > A[largest]:
        largest = r
    print "\tmaxHeapify(A,",i,")"
    print "\t",A
    print "\tl=",l,", r=",r,", largest=",largest,", heap-Size[A]=",heapSizeOfA
    if largest != i:
        print "\tA[",i,"] <=> A[",largest,"]"
        A[i],A[largest] = A[largest],A[i]
        maxHeapify(A, largest)

def buildMaxHeap(A):
    global heapSizeOfA
    
    # we neglect index 0 
    heapSizeOfA = len(A[1:])
    for i in range(len(A)/2 ,0, -1) :
        maxHeapify(A, i)

def heapSort(A):
    global heapSizeOfA
    print "buildMaxHeap(A)"
    buildMaxHeap(A)
    print "=>",A
    for i in range(len(A)-1, 1, -1):
        A[1],A[i] = A[i], A[1]
        heapSizeOfA = heapSizeOfA - 1
        print
        print "heap-Size[A]=",heapSizeOfA
        print "maxHeapify(A,1)"
        print A
        maxHeapify(A,1)

def partition(A,p,r):
    x = A[r]
    i = p - 1
    print "\tpivot: A[",r,"]=",x
    for j in range(p, r-1+1):
        if A[j] <= x:
            i = i + 1
            print "\tA[",i,"] <=> A[",j,"]"
            A[i],A[j] = A[j],A[i]
    print "\tA[",i+1,"] <=> A[",r,"]"
    A[i+1],A[r] = A[r], A[i+1]
    print "\t",A
    return i+1

def quickSort(A,p,r):
    print "quickSort(A,",p,",",r,")"
    if p < r:
        print "\tpartition(A,",p,",",r,")"
        q = partition(A,p,r)
        print "\t",q,"= pivot index"
        quickSort(A,p,q-1)
        quickSort(A,q+1,r)


def radixSort(A,d):
    print
    print "radixSort(A,",d,")"
    for i in range(0,d):
        lst = []
        lst.append('')
        for x in range(1,len(A)):
            f = str(A[x])

            # radix formatting
            b = d-len(f)
            if(b != 0):
                for v in range(b):
                    f= "0"+f
            lst.append(f[d-i-1])    

        print "digit",i+1,"=",lst

        # insertion sort 
        for j in range(2, len(lst)):
            key = lst[j]
            key_A = A[j]
            i = j - 1
            while i > 0 and lst[i] > key:
                lst[i+1] = lst[i]
                A[i+1] = A[i]
                i = i -1
            lst[i+1] = key
            A[i+1] = key_A
        print "\t=>",lst
        print "\t= ",A

        

#
# main part

# arguments processing 
sortType = ''
input = ''
for arg  in sys.argv:
    if '--' in arg: sortType = arg[2:]
    elif '.dat' in arg: input = arg
print "\nSorting Type: "+sortType
print "Input File: "+input

if input == '' or sortType == '':
    print "Wrong Argument"
    sys.exit(0);

# input data preprocessing
f = open(input,'r')
r = f.readlines()
data = []
data.insert(0,'')
for i in range(1, int(r[0])+1):
    data.insert(i,int(r[i]))

print 
print "A=",data

if sortType == "mergesort":
    print "mergeSort(inputData,1,",int(r[0]),")"
    mergeSort(data, 1, int(r[0]))
elif sortType == "heapsort":
    print "heapSort(A)"
    heapSort(data)
elif sortType == "quicksort":
    quickSort(data, 1,int(r[0]))
elif sortType == "radixsort":
    radixSort(data, 4)
else:
    print "wrong sorting type"

print
print "result: "
print data

    
